package br.ufpe.abaco.ParserGen.parser;

import br.ufpe.abaco.ParserGen.lexer.RegExp;
import java.util.*;

/**
 *  Essa classe representa um gram�tica BNF (Backus-Naur Form). Ela � formada,
 *  basicamente, por um conjunto de produ��es.
 *
 *@author     Monique Monteiro e Pablo Sampaio
 *@created    30 de Outubro de 2002
 */
public class BNFGrammar  implements java.io.Serializable  {

	/**	
	 *  Define o s�mbolo inicial da gram�tica.	
	 *
	 */
	private Vector<NonTerminalSymbol> startSymbols = new Vector<NonTerminalSymbol>();
	public Vector<NonTerminalSymbol> startSymbols() {
		return this.startSymbols;
	}
	public void startSymbol(NonTerminalSymbol symbol) {
		this.startSymbols.add(symbol);
	}

	
	

	private Production[] productions;
	//numero de producoes da gramatica	
	private int numProds;

	private TerminalSymbol[] terminals;

	//numero de simbolos terminais da gramatica	
	private int numTerminals;

	private NonTerminalSymbol[] nonTerminals;

	//numero de simbolos nao-terminais
	private int numNonTerminals;

	public BNFGrammar() {
		this.terminals = new TerminalSymbol[40];
		this.nonTerminals = new NonTerminalSymbol[40];
		this.productions = new Production[40];
		this.numProds = this.numNonTerminals = 0;
		this.terminals[0] = TerminalSymbol.EOF;
		this.numTerminals = 1;
	}
	
	public TerminalSymbol getTerminal(String name){
		return getTerminal(name, null);
	}

	/**	
	 *  Cria um novo terminal e adiciona ao array de terminais, caso o terminal	
	 *  ainda nao exista. Se ja existir um terminal com o mesmo nome, retorna o	
	 *  existente.	
	 */
	public TerminalSymbol getTerminal(String name, RegExp pattern) {
		TerminalSymbol novo;

		for (int i = 0; i < this.numTerminals; i++) {
			if (this.terminals[i].getName().equals(name)) {
				return this.terminals[i];
			}
		}

		if (this.numTerminals == this.terminals.length) {
			TerminalSymbol[] old = this.terminals;
			this.terminals = new TerminalSymbol[old.length + 40];

			for (int i = 0; i < old.length; i++) {
				this.terminals[i] = old[i];
			}

		}

		if(pattern != null){
			novo = new TerminalSymbol(name, pattern, this.numTerminals);
		}else {
			novo = new TerminalSymbol(name, this.numTerminals);
		}
		
		this.terminals[this.numTerminals] = novo;
		this.numTerminals++;

		return novo;
	}


	/**	
	* Cria um novo nao-terminal ou retorna o terminal ja existente.	
	*/
	public NonTerminalSymbol getNonTerminal(String name) {
		NonTerminalSymbol novo;

		for (int i = 0; i < this.numNonTerminals; i++) {
			if (this.nonTerminals[i].getName().equals(name)) {
				return this.nonTerminals[i];
			}
		}

		if (this.numNonTerminals == this.nonTerminals.length) {
			NonTerminalSymbol[] old = this.nonTerminals;
			this.nonTerminals = new NonTerminalSymbol[old.length + 40];

			for (int i = 0; i < old.length; i++) {
				this.nonTerminals[i] = old[i];
			}

		}

		novo = new NonTerminalSymbol(name, this.numNonTerminals);
		this.nonTerminals[this.numNonTerminals] = novo;
		this.numNonTerminals++;

		return novo;
	}

	public Production addProduction(
		NonTerminalSymbol left,
		GrammarSymbol[] right) {
		return this.addProduction(left, right, 0, Production.DEFAULT_ASSOCIATIVITY);
	}

	public Production addProduction(
		NonTerminalSymbol left,
		GrammarSymbol[] right,
		int precedence) {
		return this.addProduction(
			left,
			right,
			precedence,
			Production.DEFAULT_ASSOCIATIVITY);
	}

	public Production addProduction(
		NonTerminalSymbol left,
		GrammarSymbol[] right,
		int precedence,
		int associativity) {

		Production novo;

		if (right == null) {
			right = new GrammarSymbol[0];
		}

		novo =
			new Production(
				this,
				left,
				right,
				this.numProds,
				precedence,
				associativity);

		for (int i = 0; i < this.numProds; i++) {
			if (this.productions[i].equals(novo)) {
				return this.productions[i];
			}
		}

		if (this.numProds == this.productions.length) {
			Production[] old = this.productions;
			this.productions = new Production[old.length + 40];

			for (int i = 0; i < old.length; i++) {
				this.productions[i] = old[i];
			}

		}

		this.productions[this.numProds] = novo;
		novo.getLeftSide().numProducoes++;
		this.numProds++;

		return novo;
	}

	/**
	 *  Transforma a gramatica numa gramatica aumentada. Retorna a producao	
	 *  inicial da gramatica aumentada.	
	 */
	public Vector<Production> augment() {
		Vector<Production> result = new Vector<Production>();
		NonTerminalSymbol oldStart;

		for (NonTerminalSymbol startSymbol : startSymbols) {
			NonTerminalSymbol novo = getNonTerminal(startSymbol.getName()+"'");
			result.add(addProduction(novo, new GrammarSymbol[] { startSymbol }));
		}

		return result;
	}

	public int getNumProductions() {
		return this.numProds;
	}

	public int getNumTerminals() {
		return this.numTerminals;
	}

	public int getNumNonTerminals() {
		return this.numNonTerminals;
	}

	/**
	 *  Retorna o simbolo inicial da gramatica.	
	 */

	/**	
	 *  Retorna todas as producoes que tenham no lado esquerdo o nao-terminal	
	 *  passada como parametro.	
	 */
	public void insertProductionsOf(
		NonTerminalSymbol leftSide,
		LRState dest) {

		for (int i = 0; i < this.numProds; i++) {
			if (this.productions[i].getLeftSide() == leftSide) {
				dest.addItem(productions[i].items[0]);
			}
		}
	}

	/**	
	 *  Retorna um array com todas as producoes da gramatica.	
	 */
	public Production[] getAllProductions() {
		Production[] valor = new Production[this.numProds];

		for (int i = 0; i < valor.length; i++) {
			valor[i] = this.productions[i];
		}

		return valor;
	}

	/**	
	 *  Retorna todos os simbolos terminais da gramatica e mais o simbolo de fim	
	 *  de entrada (TerminalSymbol.EOF).	
	 */
	public TerminalSymbol[] getTerminals() {
		TerminalSymbol[] valor = new TerminalSymbol[this.numTerminals];

		for (int i = 0; i < valor.length; i++) {
			valor[i] = this.terminals[i];
		}

		return valor;
	}

	/**	
	 *  Retorna todos os simbolos nao-terminais da gramatica.	
	 */
	public NonTerminalSymbol[] getNonTerminals() {
		NonTerminalSymbol[] valor = new NonTerminalSymbol[this.numNonTerminals];

		for (int i = 0; i < valor.length; i++) {
			valor[i] = this.nonTerminals[i];
		}

		return valor;
	}


	/**
	 *  Retorna todos os s�mbolos da gram�tica (terminais e n�o-terminais).
	 */
	public GrammarSymbol[] getSymbols() {
		GrammarSymbol[] resultado =
			new GrammarSymbol[this.numTerminals + this.numNonTerminals];
		int i;
		int j;

		for (i = 0; i < this.numTerminals; i++) {
			resultado[i] = this.terminals[i];
		}

		for (j = 0; j < this.numNonTerminals; j++) {
			resultado[i + j] = this.nonTerminals[j];
		}

		return resultado;
	}

	/**
	 *  Retorna todos os conjuntos FIRST. OBS.> Eh necessario que tenha sido	
	 *  definido um simbolo inicial da gramatica.	
	 */
	public FirstSets getFirstSets() {
		return null;
		//A ser implementado...
	}

	/**	
	 *  Retorna todos os conjuntos FOLLOW. OBS.> Eh necessario que tenha sido	
	 *  definido um simbolo inicial da gramatica.	
	 */
	public FollowSets getFollowSets() {
		return null;
		//A ser implemntado...
	}

	public String toString() {
		StringBuffer resultado = new StringBuffer();

		for (int i = 0; i < this.numProds; i++) {
			resultado.append('\n');
			resultado.append(this.productions[i].toString());
		}

		return resultado.toString();
	}

	/**
	 *  Esta classe representa os conjuntos FOLLOW (definidos para cada um dos	
	 *  nao-terminais).	
	 */
	public class FollowSets {
		/*		
		 *  mapeia cada simbolo nao-terminal da gramatica num conjunto de terminais que podem		
		 *  aparecer imediatamente a direita do nao-terminal em questao		
		 */
		private Set[] follow;

		private FollowSets() {
			this.follow = new Set[numNonTerminals];
			this.calculateFollowSets();
		}

		/**
		 *  Calcula os conjuntos FOLLOW associados aos simbolos nao-terminais da		
		 *  gramatica.		
		 */
		private void calculateFollowSets() {
			Set first;
			Set follow;
			GrammarSymbol[] right;
			Set[] firstSets = this.calculateFirst();
			Production[] productions = getAllProductions();
			int prodSize = productions.length;

			//REGRA 1
			for (NonTerminalSymbol startSymbol : startSymbols)
				this.addToFollow(startSymbol, TerminalSymbol.EOF);

			//REGRAS 2 e 3
			for (int i = 0; i < prodSize; i++) {
				right = productions[i].getRightSide();

				for (int j = 0; j < right.length; j++) {
					if (right[j] instanceof NonTerminalSymbol) {
						first = this.firstOfString(firstSets, right, j + 1);
						follow = this.getFollow((NonTerminalSymbol) right[j]);

						if (first.contains(null)) {
							this.setDependency(
								productions[i].getLeftSide(),
								(NonTerminalSymbol) right[j]);
							addSpecial(follow, first);
						} else {
							follow.addAll(first);
						}
					}
				}
			}

		}

		/**
		 *  Calcula os conjuntos FIRST (de simbolos na0-terminais) para todos os		
		 *  simbolos da gramatica.O conjunto FIRST associado a um simbolo da		
		 *  gramatica contem terminais que podem iniciar strings derivadas a		
		 *  partir desse simbolo. O retorno desse metodo eh um array que mapeia		
		 *  (a partir de seus indices) os nao- terminais da gramatica nos seus		
		 *  respectivos conjuntos FIRST (representados por objetos do tipo Set).		
		 */
		private Set[] calculateFirst() {
			Set[] firstSets = new Set[numNonTerminals];
			Set first;
			int i;
			int j;

			for (i = 0; i < numNonTerminals; i++) {
				firstSets[i] = new HashSet();
				//inicializa os conjuntos FIRST
			}

			Production restante[] = new Production[numProds];
			int tamRestante = 0;
			GrammarSymbol[] right;

			for (i = 0; i < numProds; i++) {
				right = productions[i].getRightSide();

				//se o lado direito for a string vazia ou
				//se o primeiro simbolo do lado direito for um terminal ...
				if (right.length == 0 || right[0] instanceof TerminalSymbol) {
					restante[tamRestante] = productions[i];
					tamRestante++;
				}
			}

			return firstSets;
		}

		/**		
		 *  Esta funcao retorna o conjunto FIRST para uma sequencia de simbolos		
		 *  da gramatica.		
		 */
		private Set firstOfString(
			Set[] firstSets,
			GrammarSymbol[] symbols,
			int startIndex) {

			return null;
		}

		/**		
		 *  Funcao auxiliar. Ela adiciona todos os elementos do conjunto fonte		
		 *  ao conjunto destino exceto o elemento "null", que representa a		
		 *  string vazia.		
		 */
		private void addSpecial(Set destiny, Set source) {
			Iterator it = source.iterator();
			Object o;

			while (it.hasNext()) {
				o = it.next();

				if (o != null) {
					destiny.add(o);
				}
			}
		}

		/**		
		 *  Adiciona o terminal ao conjunto FOLLOW do nao-terminal.		
		 *		
		 */
		private void addToFollow(
			NonTerminalSymbol symbol,
			TerminalSymbol terminal) {
		}

		/**		
		 *  Define uma relacao de equivalencia entre os conjuntos FOLLOW de dois		
		 *  nao-terminais.		
		 *		
		 */
		private void setDependency(
			NonTerminalSymbol symbol,
			NonTerminalSymbol symbol2) {
		}

		/**		
		 *  Retorna o conjunto FOLLOW de um nao-terminal.		
		 */
		public Set getFollow(NonTerminalSymbol symbol) {
			return this.follow[symbol.index];
		}

		public String toString() {
			StringBuffer buffer = new StringBuffer();

			for (int i = 0; i < numNonTerminals; i++) {
				buffer.append("FOLLOW(");
				buffer.append(nonTerminals[i].getName());
				buffer.append("): ");
				buffer.append(this.getFollow(nonTerminals[i]));
				buffer.append('\n');
			}

			return buffer.toString();
		}

	}

	public class FirstSets {
		private Set[] firstSets;

		private FirstSets() {
			getNullables();
		}

		/**		
		 *  Retorna quais nao-terminais derivam a string vazia.		
		 *		
		 *@return    The nullables value		
		 */
		private boolean[] getNullables() {
			boolean[] isNull = new boolean[numNonTerminals];
			int[] numDependencies = new int[numNonTerminals];
			boolean[][] depends = new boolean[numNonTerminals][numNonTerminals];
			NonTerminalSymbol left;
			GrammarSymbol[] rightSide;
			int i;
			int j;
			int z;
			int symbIndex;

			for (i = 0; i < numProds; i++) {
				left = productions[i].getLeftSide();
				rightSide = productions[i].getRightSide();

				if (rightSide.length == 0) {
					isNull[left.index] = true;
					continue;
				}

				//LEMBRAR: so adicionar a dependencia se o simbolo for nao-nullable
				for (j = 0; j < rightSide.length; j++) {
					if (rightSide[j] instanceof NonTerminalSymbol) {
						symbIndex = rightSide[j].index;
						if (rightSide[j] != left
							&& !depends[left.index][symbIndex]) {
							depends[left.index][symbIndex] = true;
							numDependencies[left.index]++;

							for (z = 0; z < numNonTerminals; z++) {
								if (z != left.index
									&& depends[z][left.index]
									&& !depends[z][symbIndex]) {
									depends[z][symbIndex] = true;
									numDependencies[z]++;
								}
							}
						}
					} else {
						break;
					}
				}
			}

			printTeste(isNull, depends, numDependencies);

			return isNull;
		}

		public void printTeste(
			boolean[] nulls,
			boolean[][] depends,
			int[] nums) {
			int i;
			int j;
			System.out.println("Os nulos:");

			for (i = 0; i < nulls.length; i++) {
				System.out.print(nulls[i] + " ");
			}

			System.out.println("\nNumero de dependencias:");

			for (i = 0; i < nums.length; i++) {
				System.out.print(nums[i] + " ");
			}

			System.out.println("\nAs dependecias");

			for (i = 0; i < depends.length; i++) {
				for (j = 0; j < depends[i].length; j++) {
					System.out.print(
						depends[i][j] + (depends[i][j] ? "  " : " "));
				}

				System.out.println();
			}
		}
	}

}
